package airthmetic.exercise.backtrack;

import java.util.*;

public class _90_子集II {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Deque<Integer> queue = new ArrayDeque();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums,0,queue,used,res);
        return res;
    }

    public void backtrack(int[] nums, int start, Deque<Integer> queue, boolean[] used, List<List<Integer>> res){
        res.add(new ArrayList<Integer>(queue));

        for(int i=start; i< nums.length; i++){
            if(i>0 && nums[i] == nums[i-1] && !used[i-1]){
                continue;
            }
            queue.addLast(nums[i]);
            used[i] = true;
            backtrack(nums,i+1,queue,used,res);

            queue.removeLast();
            used[i] = false;
        }
    }
}
